home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / GCC 1.37.1r14 / usr / lib / stdlib / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-01  |  12.1 KB  |  318 lines  |  [TEXT/KAHL]
  1. #ifdef THINK_C
  2. #undef malloc
  3. #undef realloc
  4. #undef calloc
  5. #undef free
  6. #endif
  7.  
  8. /*
  9.  * Copyright (c) 1983 Regents of the University of California.
  10.  * All rights reserved.
  11.  *
  12.  * Redistribution and use in source and binary forms, with or without
  13.  * modification, are permitted provided that the following conditions
  14.  * are met:
  15.  * 1. Redistributions of source code must retain the above copyright
  16.  *    notice, this list of conditions and the following disclaimer.
  17.  * 2. Redistributions in binary form must reproduce the above copyright
  18.  *    notice, this list of conditions and the following disclaimer in the
  19.  *    documentation and/or other materials provided with the distribution.
  20.  * 3. All advertising materials mentioning features or use of this software
  21.  *    must display the following acknowledgement:
  22.  *    This product includes software developed by the University of
  23.  *    California, Berkeley and its contributors.
  24.  * 4. Neither the name of the University nor the names of its contributors
  25.  *    may be used to endorse or promote products derived from this software
  26.  *    without specific prior written permission.
  27.  *
  28.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  29.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  30.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  31.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  32.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  33.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  34.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  35.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  36.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  37.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  38.  * SUCH DAMAGE.
  39.  */
  40.  
  41. #if defined(LIBC_SCCS) && !defined(lint)
  42. static char sccsid[] = "@(#)malloc.c    5.11 (Berkeley) 2/23/91";
  43. #endif /* LIBC_SCCS and not lint */
  44.  
  45. /*
  46.  * malloc.c (Caltech) 2/21/82
  47.  * Chris Kingsley, kingsley@cit-20.
  48.  *
  49.  * This is a very fast storage allocator.  It allocates blocks of a small 
  50.  * number of different sizes, and keeps free lists of each size.  Blocks that
  51.  * don't exactly fit are passed up to the next larger size.  In this 
  52.  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
  53.  * This is designed for use in a virtual memory environment.
  54.  */
  55.  
  56. #include <sys/types.h>
  57. #include <stdlib.h>
  58. #include <string.h>
  59. #include <unistd.h>
  60.  
  61. #ifndef NULL
  62. #define    NULL 0
  63. #endif
  64.  
  65. static void morecore();
  66. static int findbucket();
  67.  
  68. /*
  69.  * The overhead on a block is at least 4 bytes.  When free, this space
  70.  * contains a pointer to the next free block, and the bottom two bits must
  71.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  72.  * byte is the size index.  The remaining bytes are for alignment.
  73.  * If range checking is enabled then a second word holds the size of the
  74.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  75.  * The order of elements is critical: ov_magic must overlay the low order
  76.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  77.  */
  78. union    overhead {
  79.     union    overhead *ov_next;    /* when free */
  80.     struct {
  81.         u_char    ovu_magic;    /* magic number */
  82.         u_char    ovu_index;    /* bucket # */
  83. #ifdef RCHECK
  84.         u_short    ovu_rmagic;    /* range magic number */
  85.         u_int    ovu_size;    /* actual block size */
  86. #endif
  87.     } ovu;
  88. #define    ov_magic    ovu.ovu_magic
  89. #define    ov_index    ovu.ovu_index
  90. #define    ov_rmagic    ovu.ovu_rmagic
  91. #define    ov_size        ovu.ovu_size
  92. };
  93.  
  94. #define    MAGIC        0xef        /* magic # on accounting info */
  95. #define RMAGIC        0x5555        /* magic # on range info */
  96.  
  97. #ifdef RCHECK
  98. #define    RSLOP        sizeof (u_short)
  99. #else
  100. #define    RSLOP        0
  101. #endif
  102.  
  103. /*
  104.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  105.  * smallest allocatable block is 8 bytes.  The overhead information
  106.  * precedes the data area returned to the user.
  107.  */
  108. #define    NBUCKETS 30
  109. static    union overhead *nextf[NBUCKETS];
  110.  
  111. static    int pagesz;            /* page size */
  112. static    int pagebucket;            /* page size bucket */
  113.  
  114. #ifdef MSTATS
  115. /*
  116.  * nmalloc[i] is the difference between the number of mallocs and frees
  117.  * for a given block size.
  118.  */
  119. static    u_int nmalloc[NBUCKETS];
  120. #include <stdio.h>
  121. #endif
  122.  
  123. #if defined(DEBUG) || defined(RCHECK)
  124. #define    ASSERT(p)   if (!(p)) botch("p")
  125. #include <stdio.h>
  126. static
  127. botch(s)
  128.     char *s;
  129. {
  130.     fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
  131.      (void) fflush(stderr);        /* just in case user buffered it */
  132.     abort();
  133. }
  134. #else
  135. #define    ASSERT(p)
  136. #endif
  137.  
  138. void *
  139. malloc(nbytes)
  140.     size_t nbytes;
  141. {
  142.       register union overhead *op;
  143.       register int bucket, n;
  144.     register unsigned amt;
  145.  
  146.     /*
  147.      * First time malloc is called, setup page size and
  148.      * align break pointer so all data will be page aligned.
  149.      */
  150.     if (pagesz == 0) 
  151.         {
  152.         pagesz = n = getpagesize();
  153.         bucket = 0;
  154.         amt = 8;
  155.         while (pagesz > amt) 
  156.             {
  157.             amt <<= 1;
  158.             bucket++;
  159.             }
  160.         pagebucket = bucket;
  161.         }
  162.     /*
  163.      * Convert amount of memory requested into closest block size
  164.      * stored in hash buckets which satisfies request.
  165.      * Account for space used per block for accounting.
  166.      */
  167.     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
  168. #ifndef RCHECK
  169.         amt = 8;    /* size of first bucket */
  170.         bucket = 0;
  171. #else
  172.         amt = 16;    /* size of first bucket */
  173.         bucket = 1;
  174. #endif
  175.         n = -(sizeof (*op) + RSLOP);
  176.     } else {
  177.         amt = pagesz;
  178.         bucket = pagebucket;
  179.     }
  180.     while (nbytes > amt + n) {
  181.         amt <<= 1;
  182.         if (amt == 0)
  183.             return (NULL);
  184.         bucket++;
  185.     }
  186.     /*
  187.      * If nothing in hash bucket right now,
  188.      * request more memory from the system.
  189.      */
  190.       if ((op = nextf[bucket]) == NULL) {
  191.           morecore(bucket);
  192.           if ((op = nextf[bucket]) == NULL)
  193.               return (NULL);
  194.     }
  195.     /* remove from linked list */
  196.       nextf[bucket] = op->ov_next;
  197.     op->ov_magic = MAGIC;
  198.     op->ov_index = bucket;
  199. #ifdef MSTATS
  200.       nmalloc[bucket]++;
  201. #endif
  202. #ifdef RCHECK
  203.     /*
  204.      * Record allocated size of block and
  205.      * bound space with magic numbers.
  206.      */
  207.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  208.     op->ov_rmagic = RMAGIC;
  209.       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  210. #endif
  211.       return ((char *)(op + 1));
  212. }
  213.  
  214. #ifdef THINK_C
  215. static void *emptyblock(size_t sz);
  216. #endif
  217.  
  218. /*
  219.  * Allocate more memory to the indicated bucket.
  220.  */
  221. static void
  222. morecore(bucket)
  223.     int bucket;
  224. {
  225.       register union overhead *op;
  226.     register int sz;        /* size of desired block */
  227.       int amt;            /* amount to allocate */
  228.       int nblks;            /* how many blocks we get */
  229.  
  230.     /*
  231.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  232.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  233.      */
  234.     sz = 1 << (bucket + 3);
  235. #ifdef DEBUG
  236.     ASSERT(sz > 0);
  237. #else
  238.     if (sz <= 0)
  239.         return;
  240. #endif
  241.     if (sz < pagesz) {
  242.         amt = pagesz;
  243.           nblks = amt / sz;
  244.     } else {
  245.         amt = sz + pagesz;
  246.         nblks = 1;
  247.     }
  248.     op = (union overhead *)emptyblock(amt);
  249.     /* no more room! */
  250.       if (!op)
  251.           return;
  252.     /*
  253.      * Add new memory allocated to that on
  254.      * free list for this hash bucket.
  255.      */
  256.       nextf[bucket] = op;
  257.       while (--nblks > 0) {
  258.         op->ov_next = (union overhead *)((caddr_t)op + sz);
  259.         op = (union overhead *)((caddr_t)op + sz);
  260.       }
  261. }
  262.  
  263. void
  264. free(cp)
  265.     void *cp;
  266. {   
  267.       register int size;
  268.     register union overhead *op;
  269.  
  270.       if (cp == NULL)
  271.           return;
  272.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  273. #ifdef DEBUG
  274.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  275. #else
  276.     if (op->ov_magic != MAGIC)
  277.         return;                /* sanity */
  278. #endif
  279. #ifdef RCHECK
  280.       ASSERT(op->ov_rmagic == RMAGIC);
  281.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  282. #endif
  283.       size = op->ov_index;
  284.       ASSERT(size < NBUCKETS);
  285.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  286.       nextf[size] = op;
  287. #ifdef MSTATS
  288.       nmalloc[size]--;
  289. #endif
  290. }
  291.  
  292. /*
  293.  * When a program attempts "storage compaction" as mentioned in the
  294.  * old malloc man page, it realloc's an already freed block.  Usually
  295.  * this is the last block it freed; occasionally it might be farther
  296.  * back.  We have to search all the free lists for the block in order
  297.  * to determine its bucket: 1st we make one pass thru the lists
  298.  * checking only the first block in each; if that fails we search
  299.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  300.  * is extern so the caller can modify it).  If that fails we just copy
  301.  * however many bytes was given to realloc() and hope it's not huge.
  302.  */
  303. int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  304.  
  305. void *
  306. realloc(cp, nbytes)
  307.     void *cp; 
  308.     size_t nbytes;
  309. {   
  310.       register u_int onb;
  311.     register int i;
  312.     union overhead *op;
  313.       char *res;
  314.     int was_alloced = 0;
  315.  
  316.       if (cp == NULL)
  317.           return (malloc(nbytes));
  318.     op = (union over